package main;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;

import tree.BinaryTreeNode;
import tree.Tree;
import utils.DegreeVector;

/**
 * This class takes a sequence representing degrees of a bipartite graph and gets a partition
 * such that the sum of the two banks of the partition is equal (and hence, bipartite).
 * @author Alex
 *
 */
public class DPSolver {
	
	private List<Double> sequence;
	private TreeMap<Double, Integer> multiplicity;
	private double sum;
	private List<DegreeVector> vectors;
	private Set<BitSet> solutions;
	
	public DPSolver(List<Double> sequence) {
		this.sequence = sequence;
		this.multiplicity = new TreeMap<Double, Integer>();
		new TreeMap<DegreeVector, Integer>();
		this.vectors = new ArrayList<DegreeVector>();
		resolveMultiplicity();
		for(Double d : this.sequence)
			sum += d;
	}
	
	public DPSolver(List<DegreeVector> dvList, int index) {
		sequence = new ArrayList<Double>();
		this.vectors = dvList;
		for(DegreeVector dv : dvList) {
			Double d = dv.getEntry(index);
			sequence.add(d);
		}
		this.multiplicity = new TreeMap<Double, Integer>();
		new TreeMap<DegreeVector, Integer>();
		resolveMultiplicity();
		for(Double d : this.sequence)
			sum += d;
	}
	
	/**
	 * Counts the number of unique occurrences of each number in the sequence.
	 */
	private void resolveMultiplicity() {
		for(Double d : this.sequence) {
			if(!this.multiplicity.containsKey(d))
				this.multiplicity.put(d, 1);
			else
				this.multiplicity.put(d, this.multiplicity.get(d) + 1);
		}
	}
	
	/**
	 * Does presudo-polynomial time dynamic programming procedure to solve PARTITION decision
	 * problem for this sequence.
	 * @return A 2d table of boolean values.
	 */
	public boolean[][] memoizeSequence() {
		if(sum % 2 != 0.0)
			return null;
		
		boolean[][] table = new boolean[this.sequence.size()][(int) (sum/2 + 1)];
		//fill out the first row
		for(int size = 0; size < table[0].length; size++) {
			double firstEntry = sequence.get(0);
			if(size == 0 || size == (int)firstEntry)
				table[0][size] = true;
			else
				table[0][size] = false;
		}	//then everything else
		for(int row = 1; row < table.length; row++) {
			for(int col = 0; col < table[0].length; col++) {
				double entry = sequence.get(row);
				if(table[row-1][col] || (entry <= col && table[row-1][(int) (col-entry)]))
					table[row][col] = true;
				else
					table[row][col] = false;
			}
		}
		return table;
	}
	
	/**
	 * Looks at the DP table and determines the members of the partition subset, working backwards.
	 * @param table
	 * @return
	 */
	public BitSet getSubsetMembers(boolean[][] table) {
		BitSet bitSet = new BitSet(this.sequence.size());
		if(table == null)
			return null;
		
		int numRows = table.length;
		int numCols = table[0].length;
		int currentRow = numRows-1;
		int currentCol = numCols-1;
		if(table[currentRow][currentCol] == false)
			return null;
		while(currentCol > 0 && currentRow >= 0) {
			double entry = this.sequence.get(currentRow);
			if((currentRow == 0) && table[currentRow][currentCol]) {
				bitSet.set(currentRow, true);
				currentRow--;
				currentCol -= entry;
			}
			else if(table[currentRow-1][(int) (currentCol-entry)] && !table[currentRow-1][currentCol]) {
				bitSet.set(currentRow, true);
				currentRow--;
				currentCol -= entry;
			}
			else {
				currentRow--;
			}
		}
		return bitSet;
	}
	
	public Tree<Integer> getAllPartitions(boolean[][] table) {
		this.solutions = new HashSet<BitSet>();
		Tree<Integer> tree = new Tree<Integer>();
		if(table == null)
			return null;
		int numRows = table.length;
		int numCols = table[0].length;
		int currentRow = numRows-1;
		int currentCol = numCols-1;
		if(table[currentRow][currentCol] == false)
			return null;
		double entry = sequence.get(currentRow);
		BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(currentRow);
		tree.setRoot(root);
		root.setLeft(new BinaryTreeNode<Integer>(currentRow-1, root));
		root.setRight(new BinaryTreeNode<Integer>(currentRow-1, root));
		expandNode(root.getLeft(), table, currentRow-1, currentCol);
		expandNode(root.getRight(), table, currentRow-1, currentCol-(int)entry);
		return tree;
	}
	
	private void expandNode(BinaryTreeNode<Integer> node, boolean[][] table, int row, int col) {
		if (node!=null && row>=0 && col>=0) {
			if ((row == 0) && table[row][col]) { //decide whether or not to include the first entry
				if (col > 0) {
					node.setRight(new BinaryTreeNode<Integer>(null, node));
					solutions.add(buildSolutionPath(node, true));
				}
				else {
					node.setLeft(new BinaryTreeNode<Integer>(null, node));
					solutions.add(buildSolutionPath(node, false));
				}
			} else if (table[row][col]) {
				double entry = sequence.get(row);
				node.setLeft(new BinaryTreeNode<Integer>(row - 1, node));
				node.setRight(new BinaryTreeNode<Integer>(row - 1, node));
				expandNode(node.getLeft(), table, row - 1, col);
				expandNode(node.getRight(), table, row - 1, col - (int) entry);
			}
		}
	}
	
	private BitSet buildSolutionPath(BinaryTreeNode<Integer> node, boolean includeFirst) {
		BitSet bitSet = new BitSet(this.sequence.size());
		bitSet.set(0, includeFirst);
		BinaryTreeNode<Integer> current = node;
		while(current.getParent() != null) {
			if(current.equals(current.getParent().getRight()))
				bitSet.set(current.getParent().getElement(), true);
			else
				bitSet.set(current.getParent().getElement(), false);
			current = current.getParent();
		}
		
		return bitSet;
	}
	
	public Set<BitSet> getSolutions() {
		return this.solutions;
	}
	
	/**
	 * Prints and returns a boolean table.
	 * @param table
	 * @return
	 */
	public String printTable(boolean[][] table) {
		StringBuilder result = new StringBuilder();
		for(int sum = 0; sum < table[0].length; sum++)
			result.append(sum).append("\t");
		result.append("\n");
		for(int sum = 0; sum < table[0].length; sum++)
			result.append("-").append("\t");
		result.append("\n");
		for(int row = 0; row < table.length; row++) {
			for(int col = 0; col < table[0].length; col++) {
				result.append(table[row][col] ? "T" : "F").append("\t");
			}
			result.append("\n");
		}
		System.out.println(result.toString());
		return result.toString();
	}

	/**
	 * @return the sequence
	 */
	public List<Double> getSequence() {
		return sequence;
	}

	/**
	 * @return the multiplicity
	 */
	public TreeMap<Double, Integer> getMultiplicity() {
		return multiplicity;
	}

	/**
	 * @return the sum
	 */
	public double getSum() {
		return sum;
	}
	
	/**
	 * @return the vectors
	 */
	public List<DegreeVector> getVectors() {
		return vectors;
	}

	/**
	 * @param vectors the vectors to set
	 */
	public void setVectors(List<DegreeVector> vectors) {
		this.vectors = vectors;
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("[DPSolver-");
		sb.append("Sequence length=").append(this.sequence.size());
		sb.append(",sum=").append(this.sum);
		sb.append("]");
		return sb.toString();
	}

}
